#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1005
#define inf 0x1fffffff
int n, m, u, v, w, sum;
int dis[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j)
                dis[i][j] = 0;
            else
                dis[i][j] = inf;
        }
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v >> w;
        dis[u][v] = min(w, dis[u][v]);//判断重边:>
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        sum += dis[1][i] + dis[i][1];
    }
    cout << sum << endl;
    return 0;
}